package q827_largestIsland;

import CommonClass.UF;

import java.util.HashSet;
import java.util.Set;

public class Solution_4 {
    int n;
    /*
    并查集解法，通过并查集即可很容易存储对应岛屿的idx及其面积
    然后穷举所有海洋格子，找出其四个方向的簇（注意用set去重）然后即可计算面积
     */
    public int largestIsland(int[][] grid) {
        this.n = grid.length;
        if (n == 1) return 1;
        UF uf = new UF(n * n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) continue;
                if (i > 1 && grid[i - 1][j] == 1) {
                    uf.union(getIndex(i, j), getIndex(i - 1, j));
                }
                if (j > 1 && grid[i][j - 1] == 1) {
                    uf.union(getIndex(i, j), getIndex(i, j - 1));
                }
                if(i + 1 <= n - 1 && grid[i + 1][j] == 1) {
                    uf.union(getIndex(i, j), getIndex(i + 1, j));
                }
                if(j + 1 <= n - 1 && grid[i][j + 1] == 1) {
                    uf.union(getIndex(i, j), getIndex(i, j + 1));
                }
            }
        }
        if (uf.getMaxConnectSize() == n * n) return n * n;
        int ans = -1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    int temp = 1;
                    for (Integer idx : getNeighbors(i, j, grid, uf)) {
                        temp += uf.getSize(idx);
                    }
                    ans = Math.max(ans, temp);
                }
            }
        }
        return ans;
    }

    private int getIndex(int i, int j) {
        return i * n + j;
    }
    private Set<Integer> getNeighbors(int i, int j, int[][] grid, UF uf) {
        Set<Integer> set = new HashSet<>();
        if(i - 1 >= 0)
            if(grid[i - 1][j] == 1)     set.add(uf.find((i - 1) * n + j));
        if( j - 1 >= 0 )
            if(grid[i][j - 1] == 1)     set.add(uf.find(i * n + j - 1)) ;
        if( i + 1 <= n - 1 )
            if(grid[i + 1][j] == 1)     set.add(uf.find((i + 1) * n + j )) ;
        if( j + 1 <= n - 1)
            if(grid[i][j + 1] == 1)     set.add(uf.find(i * n + j + 1)) ;

        return set;
    }
}
